アルゴリズム的枠組み
数値解法は、 最小化列：点の列 $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ で、$k \to \infty$ のとき $f(x^{(k)}) \to p^*$ となるもの。各ステップでは、$\Delta x$ を降下方向として、$x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$ により位置を更新します。
この章で述べる手法には適切な初期点 $x^{(0)}$ が必要です。初期点は $\text{dom } f$ 内に存在しなければならず、さらにサブレベル集合 $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ は閉集合でなければなりません。これにより、ヘッセ行列が有用な情報を提供する良好な領域内に列が留まることが保証されます。
最も単純な方向は $\Delta x = -\nabla f(x)$ですが、効率性を高めるには、通常、幾何構造の違いを考慮した 勾配降下方向によって対応する必要があります。
- 二次ノルム： $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$です。
- $L_\infty$ ノルム： $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ （座標降下法）。
2次モデルと信頼領域
ニュートン法は2次テイラー近似を使用します： $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ この二次関数は $v = \Delta x_{nt}$（ニュートンステップ）のときに最小化されます。私たちは 信頼領域：集合 $\{v \mid \|v\|_2 \le \gamma\}$を定義します。パラメータ $\gamma$ は、2次モデルに対する信頼度を反映しています。モデルが正確である場合、方向は $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ KKTシステムを用いて求めます。
- 部分最適性バウンド： $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$（$\lambda(x) < 1$ のとき有効）。
- 自己調和和： $f_1, f_2$ が自己調和的であれば、$f_1 + f_2$ も自己調和的です。
- ヘッセ行列のスパース性： 効率が得られるのは、 ヘッセ行列の帯状構造条件：$|i-j| > k$ に対して $\nabla^2 f(x)_{ij} = 0$ が成り立つ場合です。